package edu.whu.rose.clock.kps.algorithm.banks1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;

import edu.whu.rose.clock.kps.graph.GraphMatrix;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;
import edu.whu.rose.clock.util.priorityqueue.FibonacciHeapPQ;
import edu.whu.rose.clock.util.priorityqueue.UnderflowException;

public class BackwardExpandingSearch {

	private GraphMatrix graph;
	private int[][] sets;
	private int k;
	
	private int[] union;
	private FibonacciHeapPQ<DijkstraIterator> itHeap;
	private AnswerTree[] topK;
	private int size;
	
	public BackwardExpandingSearch(GraphMatrix graph, int[][] sets, int k) {
		this.graph = graph;
		this.sets = sets;
		this.k = k;
	}
	
	public static void main(String[] args) {
		GraphMatrix spg = new GraphMatrix(11012);
		spg.loadEdges("graph/edge.txt");
		
		int[][] sets = new int[][]{{300}, {400, 500}};
		
		BackwardExpandingSearch bes = new BackwardExpandingSearch(spg, sets, 10);
		bes.init();
		bes.search();
		
		for (int i = 0; i < bes.getSize(); i++) {
			AnswerTree at = bes.getAnswer(i);
			System.out.print("Rank " + (i + 1) + ": root[" + at.getRoot() + "] ");
			
			for (int j = 0; j < at.getLeafNumber(); j++) {
				int[] path = at.getPath(j);
				System.out.print("( ");
				if (path != null) {
					for (int m = 0; m < path.length; m++) {
						System.out.print(path[m] + ", ");
					}
				}
				System.out.print(" )");
			}
			System.out.println();
		}
	}
	
	public void init() {
		union = unionSets();
		itHeap= new FibonacciHeapPQ<DijkstraIterator>();
		for (int i = 0; i < union.length; i++) {
			DijkstraIterator di = new DijkstraIterator(graph, union[i]);
			itHeap.enqueue(di);
		}
		topK = new AnswerTree[k];
		size = 0;
	}
	
	private int[] unionSets() {
		SequentialIntArray sia = new SequentialIntArray();
		for (int i = 0; i < sets.length; i++) {
			int[] set = sets[i];
			for (int j = 0; j < set.length; j++) {
				sia.insert(set[j]);
			}
		}
		return sia.getArray();
	}
	
	public void search() {
		HashMap<Integer, ExpandableIntArray[]> allNodeLists = new HashMap<Integer, ExpandableIntArray[]>();
		HashMap<Integer, int[]> predecessors = new HashMap<Integer, int[]>();
		for (int i = 0; i < union.length; i++) {
			predecessors.put(new Integer(union[i]), new int[graph.getN()]);
		}
		
		while (!itHeap.isEmpty()) {
			try {
				// get the iterator with minimum next value from the heap
				DijkstraIterator di = itHeap.dequeueMin();
				int origin = di.getSource();
				SPVertex spv = di.next();
				int root = spv.getID();
				Integer V = new Integer(root);
				predecessors.get(new Integer(origin))[root - 1] = spv.getPredecessor();
				// initialize the node lists for the vertex being visited first time
				if (!allNodeLists.containsKey(V)) {
					ExpandableIntArray[] nodeLists = new ExpandableIntArray[sets.length];
					for (int i = 0; i < sets.length; i++) {
						nodeLists[i] = new ExpandableIntArray(4);
						if (Arrays.binarySearch(sets[i], origin) >= 0) {
							nodeLists[i].add(origin);
						}
					}
					allNodeLists.put(V, nodeLists);
				}
				// make sure if there are answer trees rooted on this vertex
				for (int i = 0; i < sets.length; i++) {
					if (Arrays.binarySearch(sets[i], origin) >= 0) {
						HashSet<HashSet<Integer>> tuples = crossProduct(origin, i, allNodeLists.get(V));
						if (tuples != null) {
							Iterator<HashSet<Integer>> it = tuples.iterator();
							while (it.hasNext()) {
								HashSet<Integer> tuple = it.next();
								AnswerTree at = genAnswerTree(root, tuple, origin, predecessors);
								addTopKAnswer(at);
								if (size == k) {
									return;
								}
							}
						}
						allNodeLists.get(V)[i].add(origin);
					}
				}
				// put this iterator back into the heap
				if (di.hasNext()) {
					itHeap.enqueue(di);
				}
			}
			catch (UnderflowException ex) {
				ex.printStackTrace();
			}
			
		}
	}

	private HashSet<HashSet<Integer>> crossProduct(int origin, int i, ExpandableIntArray[] nodeLists) {
		HashSet<HashSet<Integer>> results = new HashSet<HashSet<Integer>>();
		HashSet<Integer> seed = new HashSet<Integer>();
		seed.add(new Integer(origin));
		results.add(seed);
		for (int j = 0; j < nodeLists.length; j++) {
			if (j != i) {
				if (nodeLists[j].getSize() == 0) {
					return null;
				}
				ArrayList<HashSet<Integer>> tuples = new ArrayList<HashSet<Integer>>();
				Iterator<HashSet<Integer>> it = results.iterator();
				while (it.hasNext()) {
					HashSet<Integer> tuple = it.next();
					it.remove();
					for (int k = 0; k < nodeLists[j].getSize(); k++) {
						int node = nodeLists[j].get(k);
						if (node == 0) {
							continue;
						}
						Integer n = new Integer(node);
						if (!tuple.contains(n)) {
							HashSet<Integer> newTuple = new HashSet<Integer>();
							newTuple.addAll(tuple);
							newTuple.add(n);
							tuples.add(newTuple);
						}
						else {
							tuples.add(tuple);
						}
					}
				}
				results.addAll(tuples);
			}
		}
		return results;
	}
	
	private AnswerTree genAnswerTree(int root, HashSet<Integer> tuple, 
			int origin, HashMap<Integer, int[]> allPredecessors) {
		Iterator<Integer> it = tuple.iterator();
		int[] leaves = new int[tuple.size()];
		int[][] paths = new int[tuple.size()][];
		SequentialIntArray allVertexes = new SequentialIntArray();
		allVertexes.insert(root);
		int i = 0;
		
		while (it.hasNext()) {
			leaves[i] = it.next().intValue();
			paths[i] = getPath(root, leaves[i], allVertexes, 
					allPredecessors.get(new Integer(leaves[i])));
			i++;
		}
		
		return new AnswerTree(root, leaves, paths, allVertexes.getArray());
	}
	
	private int[] getPath(int root, int origin, 
			SequentialIntArray allVertexes, int[] predecessors) {
		ExpandableIntArray eia = new ExpandableIntArray();
		int current = root;
		
		while (current != origin) {
			current = predecessors[current - 1];
			if (current == 0) {
				return null;
			}
			allVertexes.insert(current);
			eia.add(current);
		}
		
		return eia.toArray();
	}
	
	private void addTopKAnswer(AnswerTree at) {
		for (int i = 0; i < size; i++) {
			int x = at.compare(topK[i]);
			if (x < 0) {
				return;
			}
			else if (x > 0) {
				System.out.println();
			}
		}
		topK[size] = at;
		size++;
	}

	public int getK() {
		return k;
	}
	
	public int getSize() {
		return size;
	}
	
	public AnswerTree[] getAnswers() {
		return topK;
	}

	public AnswerTree getAnswer(int index) {
		return topK[index];
	}
}
